class Solution(object):
    def findRedundantConnection(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        self.init(edges)

        circes = self.find_circes(1, [], set())
        # print(circes)
        for idx in range(len(edges) - 1, 0, -1):
            e = edges[idx]
            if (e[0], e[1]) in circes:
                return e
            
        return None

    def init(self, edges):
        self.n = len(edges)
        self.arr = [None] * self.n
        for i in range(self.n):
            self.arr[i] = [None] * self.n

        for e in edges:
            self.arr[e[0] - 1][e[1] - 1] = 1
            self.arr[e[1] - 1][e[0] - 1] = 1

    def find_circes(self, node, path, visited):
        # print(node, path, visited)
        if node in visited:
            idx = 0
            for p in path:
                if p[0] == node:
                    break
                idx = idx + 1
            result = set()
            for i in range(idx, len(path)):
                e = (path[i][0], path[i][1]) if path[i][0] < path[i][1] else (path[i][1], path[i][0])
                result.add(e)
            return result
        visited.add(node)
        for j in range(self.n):
            i = node - 1
            if self.arr[i][j] == 1:
                # add
                self.arr[i][j] = 0
                self.arr[j][i] = 0
                path.append([i + 1, j + 1])
                # recursive it
                result = self.find_circes(j + 1, path, visited)
                if result:
                    return result
                # restore
                path.pop()
                self.arr[i][j] = 1
                self.arr[j][i] = 1
        visited.remove(node)


if __name__ == '__main__':
    print(Solution().findRedundantConnection([[1,2],[1,3],[2,3]]))
    print(Solution().findRedundantConnection([[1,2],[2,3],[3,4],[1,4],[1,5]]))
    print(Solution().findRedundantConnection([[1,3],[3,4],[1,5],[3,5],[2,3]]))
    print(Solution().findRedundantConnection([[1,5],[3,4],[3,5],[4,5],[2,4]]))